#include <mips/regdef.h>
#include <sys/syscall.h>
#define stdinfd 	0
#define stdoutfd 	1
#ifndef 	fp
#define	fp	$fp
#endif
#define MERGE_SSIZE		(84)
#define	MERGE_RA		(76)
#define	MERGE_FP		(72)
#define	MERGE_GP		(68)
#define MERGE_S7		(56)
#define MERGE_S6		(52)
#define MERGE_S5		(48)
#define MERGE_S4		(44)
#define MERGE_S3		(40)
#define MERGE_S2		(36)
#define MERGE_S1		(32)
#define MERGE_S0		(28)
#define MERGE_ARG0	(MERGE_SSIZE)
#define MERGE_ARG1	((MERGE_SSIZE)+4)
#define MERGE_ARG2	((MERGE_SSIZE)+8)
#define MERGE_ARG3	((MERGE_SSIZE)+12)
#define MERGE_ARG4	(16)
	.text
	.align 	2
	.globl	merge
	.ent	merge

# a0: puntero a vector 1
# a1: tamaño vector 1
# a2: vector 2
# a3: tamaño vector 2
# t0: vector
merge:
	.frame fp,MERGE_SSIZE,ra
   	.set  noreorder
   	.cpload  t9
   	.set  reorder
	subu	sp,sp,MERGE_SSIZE
	.cprestore 16
	sw		ra,MERGE_RA(sp)
	sw		fp,MERGE_FP(sp)
	sw		gp,MERGE_GP(sp)
	sw		s7,MERGE_S7(sp)
	sw		s6,MERGE_S6(sp)
	sw		s5,MERGE_S5(sp)
	sw		s4,MERGE_S4(sp)
	sw		s3,MERGE_S3(sp)
	sw		s2,MERGE_S2(sp)
	sw		s1,MERGE_S1(sp)
	sw		s0,MERGE_S0(sp)
	move	fp,sp
	sw		a0,MERGE_ARG0(fp)
	sw		a1,MERGE_ARG1(fp)
	sw		a2,MERGE_ARG2(fp)
	sw		a3,MERGE_ARG3(fp)
	sw		t0,MERGE_ARG4(fp)
	lw		a0,MERGE_ARG0(fp)
	lw		a1,MERGE_ARG1(fp)
	lw		a2,MERGE_ARG2(fp)
	lw		a3,MERGE_ARG3(fp)
	lw		t0,MERGE_ARG4(fp)
	#s0: vector 1
	#s1: longitud vector 1
	#s2: vector 2
	#s3: longitud vector 2
	#s4: vector 3
	#s5: x1
	#s6: x2
	#s7: x3
	addu	s0,a0,zero #s0: vector 1
	addu	s1,a1,zero #s1: longitud vector 1
	addu	s2,a2,zero #s2: vector 2
	addu	s3,a3,zero #s3: longitud vector 2
	addu	s4,t0,zero #s4: vector 3
	addu	s5,zero,zero #s5: x1 = 0
	addu	s6,zero,zero #s6: x2 = 0
	addu	s7,zero,zero #s7: x3 = 0
	#ciclo while
merge_L0:
	bge		s5,s1,merge_LA	# x1 < tamanio 1
	bge		s6,s3,merge_LA # x2 < tamanio 2
	#obtengo el contenido de vector1[x1]
	#y vecto2[x2]
	addu	t0,s0,s5 # t0 = x1 + vector1
	lb		t1,0(t0) #t1 = vector1[x1]
	addu	t0,s2,s6 #t0 = x2 + vector2
	lb		t2,0(t0) #t2 = vector2[x2]
	#si vecto1[x1] >= vector2[x2] salta
	bge		t1,t2,else_1
	addu	t0,s4,s7 #t0 = vector3 + x3
	sb		t1,0(t0) #vector3[x3] = vector1[x1]
	addiu	s5,s5,1 #x1++
	b		merge_L0_A
else_1:
	addu	t0,s4,s7 #t0 = vector3 + x3
	sb		t2,0(t0) #vector3[x3] = vector2[x2]
	addiu	s6,s6,1 #x2++
merge_L0_A:
	# incremento x3
	addiu	s7,s7,1 #x3++
	b		merge_L0
	# fin while comenzado en merge_L0
	#segundo while
merge_LA:
	# x1 < tamaño vector 1
	bge		s5,s1,merge_LB
	# vector3[x3] = vector1[x1]
	addu	t0,s0,s5 #t0 = vector1 + x1
	lb		t1,0(t0) #t1 = vector1[x1]
	addu	t0,s4,s7 #t0 = vector3 + x3
	sb		t1,0(t0) #vector3[x3] = vector1[x1]
	addiu	s5,s5,1	#x1++
	addiu	s7,s7,1	#x3++
	b		merge_LA
	#fin segundo - while
	#tercer while
merge_LB:
	# x2 < tamaño vector 2
	bge		s6,s3,fin_merge
	# vector3[x3] = vector[x2]
	addu	t0,s2,s6 #t0 = vector2 + x2
	lb		t1,0(t0) #t1 = vector2[x2]
	addu	t0,s4,s7 #t0 = vector3+x3
	sb		t1,0(t0) #vector3[x3] = vector2[x2]
	addiu	s6,s6,1	#x2++
	addiu	s7,s7,1	#x3++
	b		merge_LB
	#fin tercer while
fin_merge:
	move	sp,fp		# destruyo stack frame
	lw		s7,MERGE_S7(sp)
	lw		s6,MERGE_S6(sp)
	lw		s5,MERGE_S5(sp)
	lw		s4,MERGE_S4(sp)
	lw		s3,MERGE_S3(sp)
	lw		s2,MERGE_S2(sp)
	lw		s1,MERGE_S1(sp)
	lw		s0,MERGE_S0(sp)
	lw		gp,MERGE_GP(sp)
	lw		fp,MERGE_FP(sp)
	lw		ra,MERGE_RA(sp)
	addiu	sp,sp,MERGE_SSIZE
	j		ra
	.end	merge

#define MERGE_SORT_SSIZE	(72)
#define	MERGE_SORT_RA		(64)
#define	MERGE_SORT_FP		(60)
#define	MERGE_SORT_GP		(56)
#define MERGE_SORT_S7		(48)
#define MERGE_SORT_S6		(44)
#define MERGE_SORT_S5		(40)
#define MERGE_SORT_S4		(36)
#define MERGE_SORT_S3		(32)
#define MERGE_SORT_S2		(28)
#define MERGE_SORT_S1		(24)
#define MERGE_SORT_S0		(20)
#define MERGE_SORT_ARG0	(MERGE_SORT_SSIZE)
#define MERGE_SORT_ARG1	((MERGE_SORT_SSIZE)+4)
	.text
	.align 	2
	.globl	merge_sort
	.ent	merge_sort

# a0: puntero a vector
# a0: tamaño del vector
merge_sort:
	.frame fp,MERGE_SORT_SSIZE,ra
   	.set  noreorder
   	.cpload  t9
   	.set  reorder
	subu	sp,sp,MERGE_SORT_SSIZE
	.cprestore 16
	sw		ra,MERGE_SORT_RA(sp)
	sw		fp,MERGE_SORT_FP(sp)
	sw		gp,MERGE_SORT_GP(sp)
	sw		s7,MERGE_SORT_S7(sp)
	sw		s6,MERGE_SORT_S6(sp)
	sw		s5,MERGE_SORT_S5(sp)
	sw		s4,MERGE_SORT_S4(sp)
	sw		s3,MERGE_SORT_S3(sp)
	sw		s2,MERGE_SORT_S2(sp)
	sw		s1,MERGE_SORT_S1(sp)
	sw		s0,MERGE_SORT_S0(sp)
	move	fp,sp
	sw		a0,MERGE_SORT_ARG0(fp)
	sw		a1,MERGE_SORT_ARG1(fp)
	lw		a0,MERGE_SORT_ARG0(fp)
	lw		a1,MERGE_SORT_ARG1(fp)
	#s0: vector
	#s1: tamaño vector
	#s2: vector 1
	#s3: tamaño vector 1
	#s4: vector 2
	#s5: tamaño vector 2
	#s6: x
	#s7: y
	addu	s0,a0,zero
	addu	s1,a1,zero
	#chequeo de tamaño
	#no salto si tamaño vector mayor a 1
	addiu	t0,zero,1
	ble		s1,t0,fin_merge_sort
	#calculo el resto y el resultado de dividir tamaño por 2
	addiu	t0,zero,2
	div		zero,s1,t0
	mflo	t0 #cargo el resultado en t0
	mfhi	t1 #cargo el resto en t1
	#si tamaño%2 igual a cero no salto
	bne		t1,zero,merge_sort_L0
	addu	s3,zero,t0	#tamaño1 = tamaño/2
	addu	s5,zero,t0  #tamaño2 = tamaño1
	b		merge_sort_L1
merge_sort_L0:
	addu	s3,t0,zero #tamaño1=tamaño/2
	addiu	s5,t0,1 #tamaño2=tamaño1+1
merge_sort_L1:
	#creo vector 1
	addu	a0,s3,zero
	la      t9,mymalloc
    jal     ra,t9
    addu	s2,v0,zero
    #creo vector 2
	addu	a0,s5,zero
	la      t9,mymalloc
    jal     ra,t9
    addu	s4,v0,zero
	#copio contenido a los vectores
	addu	s6,zero,zero
	# si x < tamanio1 no salta
	bge		s6,s3,merge_sort_L3
merge_sort_L2:
	addu	t0,s6,s0 #t0 = vector1 + x
	lb		t0,0(t0) #t0 = vector1[x]
	addu	t1,s6,s2 #t1 = vector1 + x
	sb		t0,0(t1) #vector1[x] = vector[x]
	addiu	s6,s6,1 #x++
	#verifico que x sea menor que longitud vector1
	blt		s6,s3,merge_sort_L2 #x < longitud vector2
	addu	s7,zero,zero # y = 0
	# si y < tamanio2 no salta
	bge		s7,s5,merge_sort_L4
merge_sort_L3:
	addu	t0,s6,s0 #t0 = vector + x
	lb		t0,0(t0) #t0 = vector[x]
	addu	t1,s7,s4 #t1 = vector2 + y
	sb		t0,0(t1) #vector2[y] = vector[x]
	addiu	s6,s6,1  #x++
	addiu	s7,s7,1  #y++
	#verifico que  y sea menor que longitud vector2
	blt		s7,s5,merge_sort_L3
merge_sort_L4:
	#aplico merge_sort a los vectores 1 y 2
	#vector 1
	addu	a0,s2,zero
	addu	a1,s3,zero
	la		t9,merge_sort
	jal		ra,t9
	#vector 2
	addu	a0,s4,zero
	addu	a1,s5,zero
	la		t9,merge_sort
	jal		ra,t9
	#aplico merge a todos los vectores
	addu	a0,s2,zero
	addu	a1,s3,zero
	addu	a2,s4,zero
	addu	a3,s5,zero
	addu	t0,s0,zero
	la		t9,merge
	jal		ra,t9
merge_sort_L5:
	#elimino los dos vectores
	addu	a0,s2,zero
	la      t9,myfree
    jal     ra,t9
    addu	a0,s4,zero
	la      t9,myfree
    jal     ra,t9
fin_merge_sort:
	move	sp,fp		# destruyo stack frame
	lw		s7,MERGE_SORT_S7(sp)
	lw		s6,MERGE_SORT_S6(sp)
	lw		s5,MERGE_SORT_S5(sp)
	lw		s4,MERGE_SORT_S4(sp)
	lw		s3,MERGE_SORT_S3(sp)
	lw		s2,MERGE_SORT_S2(sp)
	lw		s1,MERGE_SORT_S1(sp)
	lw		s0,MERGE_SORT_S0(sp)
	lw		gp,MERGE_SORT_GP(sp)
	lw		fp,MERGE_SORT_FP(sp)
	lw		ra,MERGE_SORT_RA(sp)
	addiu	sp,sp,MERGE_SORT_SSIZE
	j		ra
	.end	merge_sort
.data
dato:	.word 	0
